package com.suzhenyu.sort;

/**
 * 希尔排序
 * @author suzy2
 */
public class ShellSort implements Sort {
    /**
     *  插入排序的改进版。
     *  为了减少数据的移动次数，在初始序列较大时取较大的步长，
     *  通常取序列长度的一半，此时只有两个元素比较，交换一次；之后步长依次减半直至步长为1，
     *  即为插入排序，由于此时序列已接近有序，故插入元素时数据移动的次数会相对较少，效率得到了提高。
     * @param ints
     */
    @Override
    public void sort(int[] ints) {
        shellSort(ints,0,ints.length-1);
    }
    void   shellSort(int[] arr, int bgn, int end)
    {

        // 初始化步长为  长度的一半 之后步长依次减半直至步长为1
        for (int step = (end - bgn) / 2; step > 0; step /= 2)
        {
            for (int i = bgn; i < step; ++i)
            {
                /*
                 * 以下，insertSort的变异
                 */
                for (int j = i + step; j < end; j += step)
                {
                    int k = j - step;
                    for ( ; k >= i; k -= step){
                        if (arr[k] <= arr[j]){
                            break;
                        }
                    }

                    if (k != j - step)
                    {
                        int tmp = arr[j];
                        for (int m = j; m > k + step; m -= step) {
                            arr[m] = arr[m - step];
                        }
                        arr[k + step] = tmp;
                    }
                }
            }
        }
    }
}
